package problem138;


import java.util.HashMap;
import java.util.Map;

//138.随机链表的复制
//https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=top-100-liked

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node newHead = new Node(-1);
        Node tail = newHead, cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            tail.next = node;
            tail = tail.next;
            cur = cur.next;
        }
        //处理随机指针
        Node cur1 = head, cur2 = newHead.next;
        while(cur1 != null) {
            cur2.random = map.get(cur1.random);
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return newHead.next;
    }
}




















